package tools.sort;

import java.util.Vector;

public class mQuickSort
{
	/** This is a generic version of C.A.R Hoare's Quick Sort 
	* algorithm.  This will handle arrays that are already
	* sorted, and arrays with duplicate keys.<BR>
	*
	* If you think of a one dimensional array as going from
	* the lowest index on the left to the highest index on the right
	* then the parameters to this function are lowest index or
	* left and highest index or right.  The first time you call
	* this function it will be with the parameters 0, a.length - 1.
	*
	* @param a	   an integer array
	* @param lo0	 left boundary of array partition
	* @param hi0	 right boundary of array partition
	*/
    private static void QuickSort(Vector a, int l, int r) throws Exception
    {
	int M = 4;
	int i;
	int j;
	Object v;
	
	if ( (r-l) > M ) {
	    i = (r+l)/2;
	    
	    if ( ((Comparable) a.elementAt(l)).compareTo(a.elementAt(i)) > 0 ) swap(a, l, i); // Tri-Median Methode!
	    if ( ((Comparable) a.elementAt(l)).compareTo(a.elementAt(r)) > 0 ) swap(a, l, r);
	    if ( ((Comparable) a.elementAt(i)).compareTo(a.elementAt(r)) > 0 ) swap(a, i, r);
	    
	    j = r-1;
	    swap(a,i,j);
	    i = l;
	    v = (Object) a.elementAt(j);
	    for(;;) {
		while(((Comparable)a.elementAt(++i)).compareTo( v) < 0 );
		while(((Comparable)a.elementAt(--j)).compareTo(v) > 0);
		if (j<i) break;
		swap (a,i,j);
		//pause(i,j);
		//if (stopRequested) {
		//  return;
		//}
		}
	    swap(a,i,r-1);
	    //pause(i);
	    QuickSort(a,l,j);
	    QuickSort(a,i+1,r);
	}
    }
    
    private static void swap(Vector a, int i, int j) {
	Object T;
	T = a.elementAt(i); 
	a.set(i,a.elementAt(j));
	a.set(j,T);
    }
    
	private static void InsertionSort(Vector a, int lo0, int hi0) throws Exception {
	    int i;
	    int j;
	    Object v;

	    for (i=lo0+1;i<=hi0;i++) {
		v = a.elementAt(i);
		j=i;
		while ((j>lo0) && (((Comparable)a.elementAt(j-1)).compareTo(v)>0)) {
		    a.set(j,a.elementAt(j-1));
		    //    pause(i,j);
		    j--;
		}
		a.set(j,v);
	    }
	}
    
    public static void sort(Vector a) throws Exception {
    
	QuickSort(a, 0, a.size() - 1);
	InsertionSort(a,0,a.size()-1);
	//pause(-1,-1);
    }
}
